//n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 
//
// 上图为 8 皇后问题的一种解法。 
//
// 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。 
//
// 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。 
//
// 
//
// 示例： 
//
// 输入：4
//输出：[
// [".Q..",  // 解法 1
//  "...Q",
//  "Q...",
//  "..Q."],
//
// ["..Q.",  // 解法 2
//  "Q...",
//  "...Q",
//  ".Q.."]
//]
//解释: 4 皇后问题存在两个不同的解法。
// 
//
// 
//
// 提示： 
//
// 
// 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。 
// 
// Related Topics 回溯算法 
// 👍 708 👎 0

package com.leetcode.editor.cn;

import java.util.*;

//Java：N 皇后
class P51NQueens {
    public static void main(String[] args) {
        Solution solution = new P51NQueens().new Solution();
        // TO TEST
        System.out.println(solution.solveNQueens(4));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<String>> solveNQueens(int n) {
            List<List<String>> res = new LinkedList<>();
            dfs(res, new int[n], 0, n);
            return res;
        }


        void dfs(List<List<String>> res, int[] pos, int index, int n) {
            //依次检查(index, 0) 到 (index, n - 1)
            for (int i = 0; i < n; i++) {
                pos[index] = i;
                //检查当前点是否符合规则
                if (checkLegal(pos, index, i)) {
                    if (index + 1 == n) {
                        //已经到最后一行了
                        List<String> t = new LinkedList<>();
                        for (int j = 0; j < n; j++) {
                            StringBuilder sb = new StringBuilder();
                            for (int k = 0; k < n; k++) {
                                sb.append(k == pos[j] ? "Q" : ".");
                            }
                            t.add(sb.toString());
                        }
                        res.add(t);
                    } else {
                        //继续下一行
                        dfs(res, pos, index + 1, n);
                    }
                }
            }
        }

        boolean checkLegal(int[] pos, int index, int i) {
            for (int j = 0; j < index; j++) {
                if (pos[index] == pos[j]
                        || Math.abs(index - j) == Math.abs(pos[index] - pos[j])) {
                    return false;
                }
            }
            return true;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}